package LeetCode.interview;

import util.LogUtils;

/*
 * 
原题

　　Find the contiguous subarray within an array (containing at least one number) which has the largest sum. 
　　For example, given the array [−2,1,−3,4,−1,2,1,−5,4], 
the contiguous subarray [4,−1,2,1] has the largest sum = 6. 

题目大意

　　求数组的最大子数组的和。 

解题思路
	
		这道题要求 求连续的数组值，加和最大。
	
	 试想一下，如果我们从头遍历这个数组。对于数组中的其中一个元素，它只有两个选择：
	
	 1. 要么加入之前的数组加和之中（跟别人一组）
	
	 2. 要么自己单立一个数组（自己单开一组）
	
	 所以对于这个元素应该如何选择，就看他能对哪个组的贡献大。如果跟别人一组，能让总加和变大，还是跟别人一组好了；如果自己起个头一组，自己的值比之前加和的值还要大，那么还是自己单开一组好了。
	
	所以利用一个sum数组，记录每一轮sum的最大值，sum[i]表示当前这个元素是跟之前数组加和一组还是自己单立一组好，然后维护一个全局最大值即位答案。


　　动态规划问题，已知了前k个元素的最大子序列和为maxSub（已经被记录下来了），
      以及一个临时和sum，如果添加了第k+1这个元素，由于是连续子序列这个限制，所以如果k+1这个元素之前的和是小于0的，
      那么对于增大k+1这个元素从而去组成最大子序列是没有贡献的，所以可以把sum 置0。 
	
 * @Date 2017-09-13 10：01
 */
public class _053_Maximum_Subarray {
	 public int maxSubArray(int[] nums) {
		 if (nums==null || nums.length==0)	throw new RuntimeException();
		 int max = Integer.MIN_VALUE;
		 int curSum = 0;
		 for (int i : nums) {
			 /**
			  * 
			  * 因为求得是最大子序列的和，所以理论上是数组各元素遍历相加，
			  * 	假设当前元素为i，当前元素之前的和为curSum，
			  * 		假如curSum为负，那么i与curSum相加的结果反而比i本身还小。
			  * 			结论：为求最大值，负数不可加（负数越加越小）
			  * 		直接将i赋值给curSum，相当于i前的子序列结束，从i开始新开启一个子序列求和
			  * 	最后取得最大的一个子序列的和最为最大值
			  */
			 if (curSum <= 0) 
				 curSum = i;
			 else curSum += i;			//正数越加越大（可以相加(可以加入当前子序列)）
			 
			 if (max < curSum)	max = curSum;
		 }
		 return max;
	 }
	 
	 
	 /**
	  * 法二：动态规划法：
	  * 
	  * 	这是一道非常经典的动态规划的题目，用到的思路我们在别的动态规划题目中也很常用，以后我们称为”局部最优和全局最优解法“。
			基本思路是这样的，在每一步，我们维护两个变量，一个是全局最优，就是到当前元素为止最优的解是，一个是局部最优，就是必须包含当前元素的最优的解。接下来说说动态规划的递推式（这是动态规划最重要的步骤，递归式出来了，基本上代码框架也就出来了）。假设我们已知第i步的global[i]（全局最优）和local[i]（局部最优），那么第i+1步的表达式是：
			local[i+1]=Math.max(A[i], local[i]+A[i])，就是局部最优是一定要包含当前元素，所以不然就是上一步的局部最优local[i]+当前元素A[i]（因为local[i]一定包含第i个元素，所以不违反条件），但是如果local[i]是负的，那么加上他就不如不需要的，所以不然就是直接用A[i]；
			global[i+1]=Math(local[i+1],global[i])，有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优（所有情况都会被涵盖进来，因为最优的解如果不包含当前元素，那么前面会被维护在全局最优里面，如果包含当前元素，那么就是这个局部最优）。

			接下来我们分析一下复杂度，时间上只需要扫描一次数组，所以时间复杂度是O(n)。空间上我们可以看出表达式中只需要用到上一步local[i]和global[i]就可以得到下一步的结果，所以我们在实现中可以用一个变量来迭代这个结果，不需要是一个数组，也就是如程序中实现的那样，所以空间复杂度是两个变量（local和global），即O(2)=O(1)。	
	  * @param nums
	  * @return
	  */
	public int maxSubArray2(int[] nums) {  
	    if(nums==null || nums.length==0)  
	            return 0;  
	        int global = nums[0];  
	        int local  = nums[0];  
	        for(int i  = 1; i < nums.length; i ++) {  
	            local  = Math.max(local+nums[i], nums[i]);  
	            global = Math.max(local, global);  
	        }  
	        return global;  
	}  
	public static void main(String[] args) {
		LogUtils.println("结果", new _053_Maximum_Subarray().maxSubArray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}));
	}
}
